package cn.cxq.learning.tree;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;

/**
 * 剑指offer
 * 把二叉树打印成多行
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：317298
 * 本题知识点： 树 bfs
 *  算法知识视频讲解
 * 题目描述
 * 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
 * 示例1
 * 输入
 * 复制
 * {8,6,10,5,7,9,11}
 * 返回值
 * 复制
 * [[8],[6,10],[5,7,9,11]]
 */
public class LevelPrintTree {

    @Test
    public void testPrint(){
        TreeNode root = new TreeNode(8);

        TreeNode treeNode = root;

        treeNode.left = new TreeNode(4);
        treeNode.right = new TreeNode(12);
        treeNode.left.left = new TreeNode(2);
        treeNode.left.right = new TreeNode(6);
        treeNode.right.left = new TreeNode(10);
        treeNode.right.right = new TreeNode(14);
        treeNode.left.left.left = new TreeNode(1);
        treeNode.left.left.right = new TreeNode(3);
        treeNode.left.right.left = new TreeNode(5);
        treeNode.left.right.right = new TreeNode(7);
        treeNode.right.left.left = new TreeNode(9);
        treeNode.right.left.right = new TreeNode(11);
        treeNode.right.right.left = new TreeNode(13);
        treeNode.right.right.right = new TreeNode(15);

        ArrayList<ArrayList<Integer>> print = Print(root);
        System.out.println(print);
    }

    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {

        ArrayList<ArrayList<Integer>> printResult = new ArrayList<>();

        if (pRoot == null) return printResult;

        ArrayList<TreeNode> level = new ArrayList<>();
        ArrayList<Integer> levelResult = new ArrayList<>();

        level.add(pRoot);
        levelResult.add(pRoot.val);

        printResult.add(levelResult);

        levelTransversal(printResult, level);

        return printResult;
    }

    private void levelTransversal(ArrayList<ArrayList<Integer>> printResult, ArrayList<TreeNode> prelevel) {

        if (prelevel.isEmpty()) {
            return;
        }

        ArrayList<TreeNode> level = new ArrayList<>();
        ArrayList<Integer> levelResult = new ArrayList<>();

        for (TreeNode treeNode : prelevel) {
            if (treeNode.left!=null) {
                level.add(treeNode.left);
                levelResult.add(treeNode.left.val);
            }
            if (treeNode.right!=null) {
                level.add(treeNode.right);
                levelResult.add(treeNode.right.val);
            }
        }

        if (!levelResult.isEmpty()) printResult.add(levelResult);

        levelTransversal(printResult,level);
    }
}
